package pre;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-10-28 11:58
 * @version: 1.0
 * @description: 二分查找 时间复杂度(log以2为底n的对数)
 **/
public class BinarySearch {
	public static void main(String[] args) {
		int[] arr = {4,5,6,7,8,9,10,13,15,17,20,23,30};
		System.out.println(binarySearch(arr,4));
		System.out.println(binarySearch(arr,14));

	}

	private static int binarySearch(int[] arr, int i) {

		int low = 0,high = arr.length - 1;

		while(low <= high){
//			int mid = (low + high) / 2;
			int mid = low + (high - low) / 2; // 防止int值越界
			if (i == arr[mid]){
				return arr[mid];
			}else if (i < arr[mid]){
				high = mid - 1;
			}else if(i > arr[mid]){
				low = mid + 1;
			}
		}

		return -1;
	}
}
